﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Algorithms
{
    public class LinearProbingHashST<Key, Value> where Key : IComparable
    {
        private static readonly int INIT_CAPACITY = 4;

        private bool CanResize = false;
        private int N;           // number of key-value pairs in the symbol table
        private int M;           // size of linear probing table
        private Key[] keys;      // the keys
        private Value[] vals;    // the values
        private static readonly Key DefaultKValue = default(Key);
        private Dictionary<Key, int> hashValuesTable = null;

        // create an empty hash table - use 16 as default size
        public LinearProbingHashST()
            : this(INIT_CAPACITY, false)
        {
        }

        // create linear proving hash table of given capacity
        public LinearProbingHashST(int capacity, bool canResize)
            : this(capacity, canResize, null)
        {
        }

        public LinearProbingHashST(int capacity, bool canResize, Dictionary<Key, int> hashMap)
        {
            CanResize = canResize;
            M = capacity;
            keys = new Key[M];
            vals = new Value[M];
            hashValuesTable = hashMap;
        }

        // return the number of key-value pairs in the symbol table
        public int Count
        {
            get
            {
                return N;
            }
        }

        // is the symbol table empty?
        public bool IsEmpty
        {
            get
            {
                return Count == 0;
            }
        }

        // does a key-value pair with the given key exist in the symbol table?
        public bool Contains(Key key)
        {
            return GetValue(key) != null;
        }

        // hash function for keys 
        private int hash(Key key)
        {
            if (hashValuesTable == null)
            {
                //use default hash code funtion
                //returns value between 0 and M-1
                return (key.GetHashCode() & 0x7fffffff) % M;
            }
            else
            {
                return hashValuesTable[key];
            }
        }


        public override string ToString()
        {
            return string.Join(" ", keys.Select(e => e.ToString()).ToArray());
        }

        // resize the hash table to the given capacity by re-hashing all of the keys
        private void Resize(int capacity)
        {
            if (CanResize)
            {
                LinearProbingHashST<Key, Value> temp = new LinearProbingHashST<Key, Value>(capacity, CanResize);
                for (int i = 0; i < M; i++)
                {
                    if (DefaultKValue.CompareTo(keys[i]) != 0)
                    {
                        temp.Put(keys[i], vals[i]);
                    }
                }
                keys = temp.keys;
                vals = temp.vals;
                M = temp.M;
            }
        }

        // insert the key-value pair into the symbol table
        public void Put(Key key, Value val)
        {
            if (val == null)
            {
                Delete(key);
            }

            // double table size if 50% full
            if (N >= M / 2)
            {
                Resize(2 * M);
            }

            int i;

            for (i = hash(key); DefaultKValue.CompareTo(keys[i]) != 0; i = (i + 1) % M)
            {
                if (keys[i].Equals(key))
                {
                    vals[i] = val;
                    return;
                }
            }
            keys[i] = key;
            vals[i] = val;
            N++;
        }

        // return the value associated with the given key, null if no such value
        public Value GetValue(Key key)
        {
            for (int i = hash(key); DefaultKValue.CompareTo(keys[i]) != 0; i = (i + 1) % M)
            {
                if (keys[i].Equals(key))
                {
                    return vals[i];
                }
            }
            return default(Value);
        }

        // delete the key (and associated value) from the symbol table
        public void Delete(Key key)
        {
            if (!Contains(key))
            {
                return;
            }

            // find position i of key
            int i = hash(key);
            while (!key.Equals(keys[i]))
            {
                i = (i + 1) % M;
            }

            // delete key and associated value
            keys[i] = default(Key);
            vals[i] = default(Value);

            // rehash all keys in same cluster
            i = (i + 1) % M;
            while (DefaultKValue.CompareTo(keys[i]) != 0)
            {
                // delete keys[i] an vals[i] and reinsert
                Key keyToRehash = keys[i];
                Value valToRehash = vals[i];
                keys[i] = default(Key);
                vals[i] = default(Value);
                N--;
                Put(keyToRehash, valToRehash);
                i = (i + 1) % M;
            }

            N--;

            // halves size of array if it's 12.5% full or less
            if (N > 0 && N <= M / 8)
            {
                Resize(M / 2);
            }

            System.Diagnostics.Debug.Assert(Check());
        }

        // return all of the keys as in Iterable
        public IEnumerable<Key> Keys()
        {
            Queue<Key> queue = new Queue<Key>();
            for (int i = 0; i < M; i++)
            {
                if (DefaultKValue.CompareTo(keys[i]) != 0)
                {
                    queue.Enqueue(keys[i]);
                }
            }
            return queue;
        }

        // integrity check - don't check after each put() because
        // integrity not maintained during a delete()
        private bool Check()
        {
            // check that hash table is at most 50% full
            if (M < 2 * N)
            {
                Console.Error.WriteLine("Hash table size M = " + M + "; array size N = " + N);
                return false;
            }

            // check that each key in table can be found by get()
            for (int i = 0; i < M; i++)
            {
                if (DefaultKValue.CompareTo(keys[i]) == 0) continue;
                else if (!vals[i].Equals(GetValue(keys[i])))
                {
                    Console.Error.WriteLine("get[" + keys[i] + "] = " + GetValue(keys[i]) + "; vals[i] = " + vals[i]);
                    return false;
                }
            }
            return true;
        }
    }

}
